<html>
<head>
  <title>Heap</title>
  <basefont face="微软雅黑" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="Evernote Windows/307027 (zh-CN, DDL); Windows/6.1.0 (Win32);"/>
  <style>
    body, td {
      font-family: 微软雅黑;
      font-size: 10pt;
    }
  </style>
</head>
<body>
<a name="1088"/>
<h1>Heap</h1>

<div>
<span><div><div><span><font style="font-size: 16pt; color: rgb(28, 51, 135);"><b>堆</b></font></span></div><div><br/></div><div><span><font style="font-size: 12pt;"><span style="font-weight: bold;">一般情况下，堆通常指的是</span><span style="font-weight: bold;">二叉堆</span><span style="font-weight: bold;">，</span><span style="font-weight: bold;">二叉堆</span><span style="font-weight: bold;">是一个近似</span><span style="font-weight: bold;">完全二叉树</span><span style="font-weight: bold;">的数据结构，</span><span style="font-weight: bold;">即披着二叉树羊皮的数组，</span><span style="font-weight: bold;">故使用数组来实现较为便利。子结点的键值或索引总是小于（或者大于）它的父节点，且每个节点的左右子树又是一个</span><span style="font-weight: bold;">二叉堆</span><span style="font-weight: bold;">(大根堆或者小根堆)。根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。</span><span style="font-weight: bold;"><font style="color: rgb(173, 0, 0);">常被用作实现优先队列</font>。</span></font></span></div><div><br/></div><ol><li><font color="#AD0000" style="font-size: 12pt;"><span style="font-weight: bold;">以数组表示，但是以完全二叉树的方式理解</span>。</font></li><li><font color="#AD0000" style="font-size: 12pt;">唯一能够同时最优地利用空间和时间的方法——最坏情况下也能保证使用 2NlogN 次比较和恒定的额外空间。</font></li><li><font color="#E30000" style="font-size: 12pt;"><b>在索引从0开始的数组中：（节点之间的关系）</b></font></li><ul><li><font color="#E30000" style="font-size: 12pt;"><b>父节点 i 的左子节点在位置(2*i+1)</b></font></li><li><font color="#E30000" style="font-size: 12pt;"><b>父节点 i 的右子节点在位置(2*i+2)</b></font></li><li><font color="#E30000" style="font-size: 12pt;"><b>子节点 i 的父节点在位置floor((i-1)/2)</b></font></li></ul></ol><h2><br/></h2><h2><span style="line-height: 1.45;"><font style="font-size: 16pt; color: rgb(28, 51, 135);">堆的基本操作</font></span></h2><div><span style="-en-paragraph: true;">以大根堆为例，堆的常用操作如下。</span></div><ol><li><font color="#AD0000" style="font-size: 12pt;">最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点</font></li><li><font color="#AD0000" style="font-size: 12pt;">创建最大堆（Build_Max_Heap）：将堆所有数据重新排序</font></li><li><font color="#AD0000" style="font-size: 12pt;">堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算</font></li></ol><div><span style="-en-paragraph: true;"><font color="#AD0000" style="font-size: 12pt;">其中步骤1是给步骤2和3用的。</font></span></div><div><span style="-en-paragraph: true;"><font color="#AD0000" style="font-size: 12pt;"><br/></font></span></div><div><span style="-en-paragraph: true;"><font style="font-size: 16pt; color: rgb(28, 51, 135);"><b>理解</b></font></span></div><div><font color="#1C3387"><span style="font-size: 21px; line-height: 30px;"><b>：人为的规定整个二叉树的存储方式是一个数组，但显示方式（展示数据之间的逻辑结构）是完全二叉树。。。</b></span></font></div><div><br/></div><div>比如：</div><div><table style="border-collapse: collapse; min-width: 100%;"><colgroup><col style="width: 404px;"></col><col style="width: 382px;"></col><col style="width: 382px;"></col></colgroup><tbody><tr><td style="width: 404px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><img src="Heap_files/Image.jpg" type="image/jpeg" data-filename="Image.jpg" width="378"/></div></td><td style="width: 382px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><span style="-en-paragraph: true;">大顶堆，用数组表示就是：</span></div><div><font style="font-size: 14pt; color: rgb(227, 0, 0);"><b>int heap_big[]={9,6,4,5,2,1,3};</b></font></div><div><font color="#E30000"><span style="font-size: 19px; line-height: 27px;"><b>存储方式是数组，但逻辑关系是完全二叉树，所以针对这个“数组”的操作必须是根据完全二叉树的逻辑来写的。</b></span></font></div><div><font color="#E30000"><span style="font-size: 19px; line-height: 27px;"><b>这些操作包括：构建、插入、排序、查找、     </b></span></font></div><div><font color="#E30000"><span style="font-size: 19px; line-height: 27px;"><b>                      删除、等等</b></span></font></div></td><td style="width: 382px; padding: 8px; border: 1px solid rgb(204, 204, 204);"><div><img src="Heap_files/Image [1].jpg" type="image/jpeg" data-filename="Image.jpg" width="350"/><br/></div></td></tr></tbody></table></div><div><br/></div><div><font style="font-size: 16pt; color: rgb(28, 51, 135);"><b>Python</b></font></div><div><br/></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div>class MaxHeap:</div><div><span>    def __init__(self, array=None):</span></div><div><span>    <span>    if array:</span></span></div><div><span>    <span>    <span>    self.heap = self._max_heapify(array)</span></span></span></div><div><span>    <span>    else:</span></span></div><div><span>    <span>    <span>    self.heap = []</span></span></span></div><div><br/></div><div><span>    def _sink(self, array, i):</span></div><div><span>    <span>    #move node down the tree</span></span></div><div><span>    <span>    left, right = 2 * i + 1, 2 * i + 2</span></span></div><div><span>    <span>    max_index = i</span></span></div><div><span>    <span>    if left &lt; len(array) and array[left] &gt; array[max_index]:</span></span></div><div><span>    <span>    <span>    max_index = left</span></span></span></div><div><span>    <span>    if right &lt; len(array) and array[right] &gt; array[max_index]:</span></span></div><div><span>    <span>    <span>    max_index = right</span></span></span></div><div><span>    <span>    if max_index != i:</span></span></div><div><span>    <span>    <span>    array[i], array[max_index] = array[max_index], array[i]</span></span></span></div><div><span>    <span>    <span>    self._sink(array, max_index)</span></span></span></div><div><span><br/></span></div><div><span><span>    def _swim(self, array, i):</span><br/></span></div><div><span><span>    <span>    # move node up the tree</span></span><br/></span></div><div><span><span>    <span>    if i == 0:</span></span><br/></span></div><div><span><span>    <span>    <span>    return </span></span></span><br/></span></div><div><span><span>    <span>    father = (i - 1) / 2</span></span><br/></span></div><div><span><span>    <span>    if array[father] &lt; array[i]:</span></span><br/></span></div><div><span><span>    <span>    <span>    array[father], array[i] = array[i], array[father]</span></span></span><br/></span></div><div><span><span>    <span>    <span>    self._swim(array, father)</span></span></span><br/></span></div><div><span><br/></span></div><div><span><span>    def _max_heapify(self, array):</span><br/></span></div><div><span><span>    <span>    for i in xrange(len(array) / 2, -1, -1):</span></span><br/></span></div><div><span><span>    <span>    <span>    self._sink(array, i)</span></span></span><br/></span></div><div><span><span>    <span>    return array</span></span><br/></span></div><div><span><br/></span></div><div><span><span>    def push(self, item):</span><br/></span></div><div><span><span>    <span>    self.heap.append(item)</span></span><br/></span></div><div><span><span>    <span>    self._swim(self.heap, len(self.heap) -1）</span></span><br/></span></div><div><span><br/></span></div><div><span><span>    def pop(self):</span><br/></span></div><div><span><span>    <span>    self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]</span></span><br/></span></div><div><span><span>    <span>    item = self.heap.pop()</span></span><br/></span></div><div><span><span>    <span>    self._sink(self.heap, 0)</span></span><br/></span></div><div><span><span>    <span>    return item</span></span><br/></span></div><div><span><br/></span></div></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div></div><div><br/></div><div><br/></div></span>
</div></body></html> 